МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ / Аналіз складності алгоритмів ЗВІТ до лабораторної роботи № 1 з дисципліни " AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ"  МЕТА РОБОТИ Оволодіти методикою аналізу складності основних алгоритмічних конструкцій. Навчитись обчислювати функцію трудомісткості. Ознайомитись з класифікацією алгоритмів на основі функції трудомісткості. Опанувати методику аналізу розроблених алгоритмів на предмет їх складності. ТЕОРЕТИЧНІ ВІДОМОСТІ 2.1. Поняття алгоритму В старому трактуванні алгоритм - це точний набір інструкцій, що описують послідовність дій деякого виконавця для досягнення результату, рішення деякого завдання за кінцевий час. У зв'язку з розвитком паралельності в роботі комп'ютерів слово «послідовність» стали заміняти більше загальним словом «порядок». Це пов'язане з тим, що якісь дії алгоритму повинні бути виконані тільки один за одним, але якісь можуть бути й незалежними. Поняття алгоритму необов'язково відноситься до комп'ютерних програм, так, наприклад, чітко описаний рецепт готування блюда також є алгоритмом, у такому випадку виконавцем є людина. Однак найчастіше як виконавець виступає комп'ютер. Єдиного «правдивого» визначення поняття «алгоритм» немає. «Алгоритм - це всяка система обчислень, що виконуються по строго визначеним правилам, які після певного числа кроків свідомо приводять до рішення поставленого завдання.» (А. Колмогоров) «Алгоритм - це послідовність дій, спрямованих на одержання певного результату за кінцеве число кроків.» (ROXANstudio) «Алгоритм є формалізована послідовність дій (подій). Алгоритм може бути записаний словами і зображений схематично. Практично будь-яка невипадкова повторювана дія піддається опису через алгоритм.» ([grey_olli]) «Алгоритм - однозначно, доступно і коротко описана послідовність процедур для відтворення процесу з обумовленим завданням алгоритму результатом при заданих початкових умовах. Універсальність (або спеціалізація) алгоритму визначається застосовністю і надійністю даного алгоритму для рішення нестандартних завдань.» 2.2. Складність алгоритмів Для оцінки алгоритмів існує багато критеріїв. Найбільшу увагу приділяють порядку росту, необхідного для розв'язання задачі часу та розміру пам'яті при збільшені вхідних даних. З кожною конкретною задачею зв'язане число, яке називається розміром задачі і яке виражає міру кількості вхідних даних. Наприклад, розміром задачі множення матриць може бути найбільший розмір матриць-співмножників. Розміром задачі про графи може бути число ребер даного графа. Час, який витрачається алгоритмом, як функція розміру задачі, називається часовою складністю цього алгоритму. T(n). Асимптотику поведінки цієї функції при збільшенні розміру задачі називають асимптотичною часовою складністю, а для її позначення використовують нотацію Ландау (велике O). Аналогічно, можна виділити просторову складність та асимптотичну просторову складність. Саме асимптотична складність визначає розмір задач, які алгоритм здатен обробити. Наприклад, якщо алгоритм обробляє вхідні дані розміром n за час cn², де c - деяка стала, то кажуть, що часова складність такого алгоритму O(n²). Просторова та часова складності як функції від розмірів задачі є дві фундаментальні оцінки ефективності при аналізі алгоритмів. ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ Варіант 1 Розробити алгоритм розв'язання задачі згідно з індивідуальним завданням. Визначити до якого класу (підкласу) належить цей алгоритм в залежності від тих факторів, що впливають на значення функції трудомісткості. Знайти функцію трудомісткості алгоритму, використовуючи методику аналізу основних алгоритмічних конструкцій та визначення набору "елементарних" операцій. Визначити часову складність алгоритму для великих розмірів вхідних даних. Для її позначення використати нотацію Ландау (велике O). Навести назву асимптотичного класу ефективності алгоритму. Пояснити, як збільшиться час роботи алгоритму при подвоєнні розміру задачі. Побудувати ...